package 算法;

/**
 * 归并排序，时间复杂度为O(nlogn)
 * @author firebroo
 * 递推公式 T(n) = 2T(n/2) + O(n) 应用主定理第二条T(n) = O(n^(lgb(a))=O(nlgn)
 */
public class MergeSort {
	/**
	 *  递归 
	 * @return
	 */
	public static int[] sort(int[] data,int low, int high){
		int mid=(low+high)/2;
		if(low < high){
			sort(data, low, mid);
			sort(data, mid+1,high);
			merge(data,low,mid,high);
		}
		return data;
	}
	public static void merge(int[] data, int low,int mid,int high){
		int[] temp=new int[high-low+1];
		int i=low;
		int j=mid+1;
		int k=0;
		
		while(i <=mid && j<=high){
			if(data[i] < data[j]){
				temp[k++] =data[i++];
			}else{
				temp[k++]=data[j++];
			}
		}
		while(i<=mid){
			temp[k++]=data[i++];
		}
		while(j<=high){
			temp[k++] =data[j++];
		}
		for(int i1=0;i1<temp.length;i1++){
			data[i1+low]=temp[i1];
		}
	}

	public static void main(String[] args){
		int[] data={2,3,43,3,5,67,5};
		MergeSort.sort(data,0,data.length-1);
		//System.out.println(Arrays.toString(data));
		for(int i=0;i<data.length;i++){
			System.out.println(data[i]);
		}
	}
}
